#ifndef PRIM_HEAD
#define PRIM_HEAD
#include<iostream>
using namespace std;

class graph{
public:
    int **adjGraph;//original initiated graph
    int **primGraph;//to stroe selected edges
    int **prim_temp_graph;//to process prim
    int *mark;//mark[i]=1,if vertex number "i" is picked out during the process.
    int *prim_visited_node;
    int current_vertex_num=0;//counting the number of vertexes that is included

    graph();
    ~graph();
    void set_edge(int st,int en,int w);
    int first_edge(int i);
    int next_edge(int i,int j);

    void prim_process();
};

void show(int**);





void graph::prim_process(){
    mark[0]=1;
    prim_visited_node[0]=0;
    current_vertex_num++;

    while(current_vertex_num<6){
        for(int i=0;i<6;i++)
            for(int j=0;j<6;j++)
                prim_temp_graph[i][j]=-1;
        for(int i=0;i<current_vertex_num;i++){
            int j=prim_visited_node[i];
            for(int k=first_edge(j);;k=next_edge(j,k)){
                if(k!=-1){
                    if(mark[k]==0&&adjGraph[j][k]>0)
                        prim_temp_graph[j][k]=adjGraph[j][k];
                }
                else break;
            }
        }

        int tmp=1e3;
        int a=0;
        int b=0;
        for(int i=0;i<6;i++)
            for(int j=0;j<6;j++){
                if(tmp>prim_temp_graph[i][j]&&prim_temp_graph[i][j]!=-1){
                    tmp=prim_temp_graph[i][j];
                    a=i;b=j;
                }
            }
        primGraph[a][b]=adjGraph[a][b];
        if(mark[a]==0)
        {
            mark[a]=1;
            prim_visited_node[current_vertex_num]=a;
            current_vertex_num++;
        }
        if(mark[b]==0){
            mark[b]=1;
            prim_visited_node[current_vertex_num]=b;
            current_vertex_num++;
        }
        cout<<a<<"  "<<b<<"  "<<primGraph[a][b];
    }


}


int graph::first_edge(int i){
    for(int j=0;j<6;j++)
    {
        if(adjGraph[i][j]>0)
            return j;
    }
    return -1;
}

int graph::next_edge(int i, int j){
    for(int k=j+1;k<6;k++){
        if(adjGraph[i][k]>0)
            return k;
    }
    return -1;
}

void graph::set_edge(int st, int en, int w){
    adjGraph[st-1][en-1]=w;
    adjGraph[en-1][st-1]=w;
}

graph::graph(){
    adjGraph=(int **)new int*[6];
    prim_temp_graph=(int**)new int*[6];
    primGraph=(int **)new int*[6];
    for(int i=0;i<6;i++){
        adjGraph[i]=new int[6];
        prim_temp_graph[i]=new int[6];
        primGraph[i]=new int[6];
    }
    mark=new int[6];
    prim_visited_node=new int[6];


    for(int i=0;i<6;i++){
        mark[i]=0;
        prim_visited_node[i]=-1;
        for(int j=0;j<6;j++){
            adjGraph[i][j]=-1;
            primGraph[i][j]=-1;
        }
    }
}

graph::~graph(){
    for(int i=0;i<6;i++){
        delete adjGraph[i];
        delete primGraph[i];
        delete prim_temp_graph[i];
    }
    delete primGraph;
    delete adjGraph;
    delete prim_temp_graph;
    delete mark;
    delete prim_visited_node;
}

void show(int **matrix){
    for(int i=0;i<6;i++){
        for(int j=0;j<6;j++){
            if(matrix[i][j]>0)
                cout<<matrix[i][j]<<"    ";
            else cout<<"*"<<"    ";
        }
        cout<<endl<<endl;
    }
}

#endif // PRIM_HEAD

